{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Strong Pair XOR I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #trie #array #hash-table #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #字典树 #数组 #哈希表 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumStrongPairXor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出强数对的最大异或值 I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> 。如果一对整数 <code>x</code> 和 <code>y</code> 满足以下条件，则称其为 <strong>强数对</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>|x - y| &lt;= min(x, y)</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>你需要从 <code>nums</code> 中选出两个整数，且满足：这两个整数可以形成一个强数对，并且它们的按位异或（<code>XOR</code>）值是在该数组所有强数对中的<strong> 最大值 </strong>。</p>\n",
    "\n",
    "<p>返回数组 <code>nums</code> 所有可能的强数对中的<strong> 最大 </strong>异或值。</p>\n",
    "\n",
    "<p><strong>注意</strong>，你可以选择同一个整数两次来形成一个强数对。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,4,5]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>数组<code> nums </code>中有 11 个强数对：(1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) 和 (5, 5) 。\n",
    "这些强数对中的最大异或值是 3 XOR 4 = 7 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [10,100]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>数组<code> nums </code>中有 2 个强数对：(10, 10) 和 (100, 100) 。\n",
    "这些强数对中的最大异或值是 10 XOR 10 = 0 ，数对 (100, 100) 的异或值也是 100 XOR 100 = 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5,6,25,30]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>数组<code> nums </code>中有 6 个强数对：(5, 5), (5, 6), (6, 6), (25, 25), (25, 30) 和 (30, 30) 。\n",
    "这些强数对中的最大异或值是 25 XOR 30 = 7 ；另一个异或值非零的数对是 (5, 6) ，其异或值是 5 XOR 6 = 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-strong-pair-xor-i](https://leetcode.cn/problems/maximum-strong-pair-xor-i/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-strong-pair-xor-i](https://leetcode.cn/problems/maximum-strong-pair-xor-i/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]', '[10,100]', '[5,6,25,30]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        max_bitwise_value = 0\n",
    "        for i in range(N):\n",
    "            for j in range(i, N):\n",
    "                # strong pair\n",
    "                if abs(nums[i]-nums[j])<=min(nums[i], nums[j]):\n",
    "                    # bitwise xor\n",
    "                    xor_value = nums[i]^nums[j]\n",
    "                    max_bitwise_value = max(max_bitwise_value, xor_value)\n",
    "        return max_bitwise_value\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            for j in range(i, n):\n",
    "                y = nums[j]\n",
    "                if abs(x - y) <= min(x, y):\n",
    "                    res = max(res, x ^ y)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        l=[]\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if abs(nums[i]-nums[j])<=min(nums[i],nums[j]):\n",
    "                    l.append(nums[i]^nums[j])\n",
    "        if l==[]:return 0\n",
    "\n",
    "        return max(l)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if abs(nums[i]-nums[j])<=min(nums[i],nums[j]):\n",
    "                    ans=max(ans,nums[i]^nums[j])\n",
    "        return ans "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
